#include <bits/stdc++.h>
using namespace std;
int p, t, n, m;
int fac[6000000], inv[6000000];
int power(int x, int y)
{
    int res = 1;
    while (y)
    {
        if (y & 1)
        {
            res = 1ll * res * x % p;
        }
        x = 1ll * x * x % p;
        y >>= 1;
    }
    return res;
}
int C(int x, int y)
{
    if (y < 0 || y > x)
    {
        return 0;
    }
    return 1ll * fac[x] * inv[y] % p * inv[x - y] % p;
}
int main()
{
    freopen("pr.in", "r", stdin);
    freopen("pr.out", "w", stdout);
    scanf("%d%d", &p, &t);
    fac[0] = 1;
    for (int i = 1; i <= 5000000; i++)
    {
        fac[i] = 1ll * fac[i - 1] * i % p;
    }
    inv[5000000] = power(fac[5000000], p - 2);
    for (int i = 5000000; i; i--)
    {
        inv[i - 1] = 1ll * inv[i] * i % p;
    }
    while (t--)
    {
        int ans = 0;
        scanf("%d%d", &n, &m);
        for (int i = 0, c = 1; i <= n; i++, c = -c)
        {
            ans = (ans + 1ll * c * C(n * m + 2 * n - 1 - i * (m + 1), 2 * n - 1) * C(2 * n, i)) % p;
        }
        printf("%lld\n", (p + 1ll - 1ll * ans * power(power(m + 1, 2 * n), p - 2) % p) * power(2, p - 2) % p);
    }
    return 0;
}